A triangular matrix is a type of square matrix that has only zero elements above or below the main diagonal of the matrix. A lower triangular matrix has only zero elements above the main diagonal, such that any nonzero elements in the matrix are in the lower triangle, on or below the main diagonal. An upper triangular matrix has only zero elements below the main diagonal, such that any nonzero elements in the matrix are in the upper triangle, on or above the main diagonal. A triangular matrix can be used to represent a system of equations in the field of linear algebra.
A sparse triangular matrix is a triangular matrix that has a substantial number of zero elements in the populated triangle; for example, a sparse lower triangular matrix has one or more zero values in its lower triangle. A sparse triangular solve (SpTS) is process for solving for the vector x in the equation Ax=y, where A is a sparse triangular matrix with N rows and N columns, x is a vector with N unknown values, and y is a vector of N known values. If the only non-zero values in the matrix A are on the main diagonal and on one side of that diagonal, it is possible to solve for the vector x using substitution. Solving for a vector entry x[n] relies on having solved all previous vector entries (e.g., x[0]-x[n−1]) in the case of forward substitution in a lower triangular matrix. However, if the matrix is sparse, some of the triangular matrix values are also zero and it is possible to solve multiple rows in parallel, on parallel processors.